package Algorithm.interview;

/**
 * @Author self
 * @Date 2024/9/7 14:55
 * @Describe LRU（Least Recently Used）缓存算法是一种常用的缓存淘汰策略，
 * 它根据最近使用的时间来淘汰不常使用的缓存数据。具体来说，当缓存满时，它会移除最近最少使用的数据。
 */

/*LRU 算法的关键点
        使用一个哈希表来快速查询数据。
        使用一个双向链表来记录数据的使用顺序，最常使用的数据在链表头部，最少使用的数据在链表尾部。
        当数据被访问时，将其移动到链表头部。
        当缓存满时，将链表尾部的数据（即最近最少使用的数据）移除。
        为了实现 LRU 算法，通常我们使用 HashMap 和 双向链表：

        HashMap 用来快速定位缓存中的数据。
        双向链表 维护数据的使用顺序。*/
import java.util.HashMap;

class LRUCache<K, V> {
    // 定义双向链表的节点
    private class Node {
        K key;
        V value;
        Node prev;
        Node next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;  // LRU缓存的容量
    private HashMap<K, Node> cache;  // 存储缓存内容
    private Node head, tail;  // 伪头和伪尾节点，用于维护双向链表

    // 初始化 LRU 缓存
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node(null, null);  // 哨兵头节点
        this.tail = new Node(null, null);  // 哨兵尾节点
        head.next = tail;
        tail.prev = head;
    }

    // 获取缓存中的值
    public V get(K key) {
        Node node = cache.get(key);
        if (node == null) {
            return null;  // 如果key不存在，返回null
        }
        // 如果key存在，先移除当前节点，再将它放到链表头部
        moveToHead(node);
        return node.value;
    }

    // 将键值对放入缓存
    public void put(K key, V value) {
        Node node = cache.get(key);
        if (node != null) {
            // 如果键已存在，更新其值，并移到头部
            node.value = value;
            moveToHead(node);
        } else {
            // 如果键不存在，创建新的节点
            Node newNode = new Node(key, value);
            // 将新节点添加到链表头部
            addToHead(newNode);
            // 将新节点加入缓存
            cache.put(key, newNode);
            // 如果缓存超出容量，移除尾部最不常用的节点
            if (cache.size() > capacity) {
                Node tailNode = removeTail();
                cache.remove(tailNode.key);  // 从缓存中移除该节点
            }
        }
    }

    // 将节点移动到链表头部
    private void moveToHead(Node node) {
        removeNode(node);  // 先移除节点
        addToHead(node);   // 然后将节点添加到头部
    }

    // 移除链表中的节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 将节点添加到链表头部
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // 移除链表尾部的节点（最近最少使用的节点）
    private Node removeTail() {
        Node tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }

    public static void main(String[] args) {
        // 创建容量为3的LRU缓存
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);

        lruCache.put(1, "one");
        lruCache.put(2, "two");
        lruCache.put(3, "three");
        System.out.println(lruCache.get(1));  // 访问key为1的值 "one"

        lruCache.put(4, "four");  // 插入key为4，导致key为2的值被淘汰
        System.out.println(lruCache.get(2));  // 访问key为2，返回null，因其被淘汰

        lruCache.put(5, "five");  // 插入key为5，淘汰最近最少使用的key为3
        System.out.println(lruCache.get(3));  // 访问key为3，返回null，因其被淘汰
    }
}

